|
In linear algebra, a Toeplitz matrix or diagonal-constant matrix, named after Otto Toeplitz, is a square matrix in which each descending diagonal from left to right is constant, e.g.: : Any ''n''×''n'' matrix ''A'' of the form : is a Toeplitz matrix. If the ''i'',''j'' element of ''A'' is denoted ''A''''i'',''j'', then we have : ==Solving a Toeplitz system== A matrix equation of the form : is called a Toeplitz system if ''A'' is a Toeplitz matrix. If ''A'' is an Toeplitz matrix, then the system has only 2''n''−1 degrees of freedom, rather than ''n''2. We might therefore expect that the solution of a Toeplitz system would be easier, and indeed that is the case. Toeplitz systems can be solved by the Levinson algorithm in ''Θ''(''n''2) time. Variants of this algorithm have been shown to be weakly stable (i.e. they exhibit numerical stability for well-conditioned linear systems). The algorithm can also be used to find the determinant of a Toeplitz matrix in ''O''(''n''2) time. A Toeplitz matrix can also be decomposed (i.e. factored) in ''O''(''n''2) time. The Bareiss algorithm for an LU decomposition is stable. An LU decomposition gives a quick method for solving a Toeplitz system, and also for computing the determinant. Algorithms that are asymptotically faster (in finite arithmetic, i.e., given a tolerance the exact solution is obtained within the tolerance ) than those of Bareiss and Levinson have been described in the literature. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Toeplitz matrix」の詳細全文を読む スポンサード リンク
|